#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef Bintree Datatype;
typedef struct QueueNode
{
	Datatype val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;


void QueueInit(Queue* Q);
void QueuePush(Queue* Q, Datatype x);
void QueuePop(Queue* Q);
Datatype QueueRead(Queue* Q);
bool QueueEmpty(Queue* Q);
void QueueDestroy(Queue* Q);


void QueueInit(Queue* Q)
{
	assert(Q);

	Q->head = NULL;
	Q->tail = NULL;
}

QNode* BuyQNode(Datatype x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

void QueuePush(Queue* Q, Datatype x)
{
	assert(Q);

	if (!Q->head)
	{
		Q->head = Q->tail = BuyQNode(x);
	}
	else
	{
		QNode* newnode = BuyQNode(x);
		Q->tail->next = newnode;
		Q->tail = newnode;
	}
}

void QueuePop(Queue* Q)
{
	assert(Q);
	assert(!QueueEmpty(Q));

	if (Q->head == Q->tail)
	{
		free(Q->head);
		Q->head = Q->tail = NULL;
	}
	else
	{
		QNode* next = Q->head->next;
		free(Q->head);
		Q->head = next;
	}
}

Datatype QueueRead(Queue* Q)
{
	assert(Q);
	assert(!QueueEmpty(Q));

	return Q->head->val;
}

bool QueueEmpty(Queue* Q)
{
	assert(Q);

	return Q->head == NULL;
}

void QueueDestroy(Queue* Q)
{
	assert(Q);

	while (Q->head)
	{
		QNode* next = Q->head->next;
		free(Q->head);
		Q->head = next;
	}

}
